PrecSezione 8.3: Sistema di servizio orientato alla perdita SuCapitolo 8: Traffico, code e reti a pacchetto Sezione 8.5: Reti per trasmissione datiSegue

## 8.4Sistemi di servizio orientati al ritardo↓

Mentre i sistemi orientati alla perdita rappresentano il modo di operare delle reti di telecomunicazione a commutazione di circuito, in cui ogni connessione impegna in modo esclusivo alcune risorse di rete, che una volta esaurite producono un rifiuto della richiesta di connessione, i sistemi orientati al ritardo sono rappresentativi di reti a commutazione di pacchetto↓, in cui i messaggi sono suddivisi in unità elementari (detti pacchetti, appunto) la cui ricezione non deve più avvenire in tempo reale, e che condividono le stesse risorse fisiche (degli organi di commutazione e di trasmissione) con i pacchetti di altre comunicazioni. Pertanto, l’invio di un pacchetto può essere ritardato se il sistema di servizio è in grado di gestire delle code di attesa↓, in cui accumulare le richieste che eccedono il numero di serventi a disposizione, e da cui prelevare (con ritardo) i pacchetti stessi non appena si rendano disponibili le risorse trasmissive necessarie.
In questo caso, il grafico che mostra la ripartizione dei flussi di richieste si modifica come in figura, dove è evidenziato come la frequenza di richieste λo si suddivide tra la frequenza delle richieste perse λp, quelle servite con ritardo λsr, e quelle servite immediatamente λsi, in funzione della probabilità di perdita Pp e di ritardo Pr. Nei termini di queste quantità, valgono le relazioni:
λp=Ppλo; λsr=Pr(1  −Pp)λo; λsi=(1 −Pr)(1 −Pp)λo
Indicando con τS=(1)/(μ) il tempo medio di servizio di ogni richiesta, (che non comprende quindi il tempo di accodamento), si definisce, come già noto, una intensità di traffico offerto Ao=(λo)/(μ)=λoτS, che deve risultare
Ao=Ap+Asr+Asi e quindi Asr=(λsr)/(μ),Asi=(λsi)/(μ)
Considerando il caso in cui la coda abbia una lunghezza finita e pari ad L, osserviamo che, a prima vista, anche le L richieste successive all’impegno di tutti gli M serventi sono accolte (e poste in coda), come se i serventi fossero divenuti M+L. In realtà l’analisi fornisce risultati differenti, in quanto le richieste accodate devono essere ancora servite, e quindi il calcolo della Pp non è una diretta estensione dei risultati ottenuti per i sistemi orientati alla perdita. E’ comunque abbastanza semplice verificare [301] [301]Se PB è la probabilità di blocco derivante dalla disponibilità di M serventi, una frequenza di richieste pari a PB⋅λo non può essere servita immediatamente; adottando una coda, la frequenza delle richieste non servite immediatamente PB⋅λo è uguale a λo(Pp+Pr(1 −Pp)), ed eguagliando le due espressioni si ottiene Pp=(PB−Pr)/(1 −Pr), che è sempre minore di PB. che ora la Pp risulta inferiore alla PB del caso senza coda, e pertanto l’intensità di traffico smaltito As=Asr+Asi=(1 −Pp)Ao aumenta, a parità di offerta.

### 8.4.1Risultato di Little↓

Si tratta di un risultato molto generale, valido per qualsiasi distribuzione dei tempi di interarrivo e di servizio, la cui applicazione può tornare utile nell’analisi, e che recita:

> Il numero medio N di utenti contemporaneamente presenti in un sistema di servizio è pari al prodotto tra frequenza media di smaltimento delle richieste λs ed il tempo medio di permanenza τp dell’utente nel sistema

e quindi in definitiva N=λs⋅τp. Nell’applicazione al caso di servizi orientati alla perdita, si ha τp=τS, mentre nei servizi a coda risulta τp=τc+τS in cui τc rappresenta il tempo medio di coda.

### 8.4.2Sistemi a coda infinita↓ ed a servente unico

Prima di fornire risultati più generali, svolgiamo l’analisi per questo caso particolare, in cui la frequenza di richieste perse λp è nulla, dato che una coda di lunghezza infinita le accoglie comunque tutte.
Il sistema è descritto da un punto di vista statistico mediante il diagramma di nascita e morte riportato a fianco, in cui ogni stato Sk rappresenta k richieste nel sistema, di cui una sta ricevendo servizio e k− 1 sono accodate.
Per procedere nell’analisi, si applica lo stesso principio di equilibrio statistico già adottato a pag. 1↑, il quale asserisce che, esaurito un periodo transitorio iniziale, la frequenza media delle transizioni tra Sk e Sk+ 1 deve eguagliare quella da Sk+ 1 ad Sk. Indicando con pk=Pr(Sk) la probabilità che il sistema contenga k richieste, l’equilibrio statistico si traduce nell’insieme di equazioni
(17.21) λopk=μpk+ 1 con k= 0, 1, 2, …, ∞
Infatti, in base alle stesse considerazioni svolte nella prima parte della nota 8.3.3↑ di pag. 1↑, λopk è pari alla frequenza media (frazione di λo) con cui il numero di richieste accolte passa da k a k+ 1; essendo il servente unico, la frequenza di servizio è sempre μ=(1)/(τS), indipendentemente dal numero di richieste accodate, e dunque μpk+ 1 è proprio la frequenza media con cui il sistema passa da k+ 1 a k richieste accolte.
La relazione (17.21↑) è di natura ricorsiva, e può esprimersi come
pk=⎛⎝(λo)/(μ)⎞⎠kp0=Akop0
Per determinare il valore p0=Pr(S0), uguale alla probabilità che il sistema sia vuoto, ricordiamo [302] [302]Nella derivazione del risultato si fa uso della relazione ∑∞k= 0αk=(1)/(1 −α), nota con il nome di serie geometrica, e valida se α< 1, come infatti risulta nel nostro caso, in quanto necessariamente deve risultare Ao=(λo)/(μ)< 1; se il servente è unico infatti, una frequenza di arrivo maggiore di quella di servizio preclude ogni speranza di funzionamento, dato che evidentemente il sistema non ha modo di smaltire in tempo le richieste che si presentano. che deve risultare
1 =∞⎲⎳k= 0pk=∞⎲⎳k= 0p0Ako=p0(1)/(1  −Ao)
da cui otteniamo p0= 1 −Ao e dunque
pk=(1  −Ao)Ako
che corrisponde ad una densità di probabilità esponenziale discreta.
Siamo ora in grado di determinare alcune grandezze di interesse:
Probabilità di ritardo↓ Pr:risulta pari alla probabilità che il sistema non sia vuoto, e cioè che ci sia già almeno una richiesta accolta, ed è pari a [303] [303]Ricordiamo che p0 è la probabilità che il sistema sia vuoto, e dunque 1  −p0 quella che non sia vuoto.
Pr= 1 −po= 1 −(1 −Ao)=Ao
Ricordiamo di aver già definito l’efficienza come il rapporto ρ=(As)/(M) tra il traffico smaltito ed il numero dei serventi; nel nostro caso M= 1 e As=Ao: dunque ρ=Ao. Pertanto, il risultato Pr=Ao=ρ indica come, al tendere ad 1 dell’efficienza, la probabilità di ritardo tenda anch’essa ad 1.
Lunghezza media di coda↓indicata con L: risulta essere semplicemente il valore atteso del numero di richieste presenti nel sistema, ovvero [304] [304] si fa uso della relazione ∑∞k= 0kαk=α∑∞k= 0kαk− 1= α(∂)/(∂α)∑∞k= 0αk=α(∂)/(∂α)(1)/(1 −α)=(α)/((1  −α)2)
L=E{k}=∞⎲⎳k= 0kpk=(1  −Ao)∞⎲⎳k= 0kAko=(Ao)/(1 −Ao)
da cui risulta che per Ao→ 1 la coda tende ad una lunghezza infinita.
Tempo medio di permanenzaindicato con τp, e scomponibile nella somma τp=τS+τc tra il tempo medio di servizio ed il tempo medio di coda. Possiamo applicare qui il risultato di Little N=λs⋅τp, che esprime la relazione tra numero medio N di richieste presenti, frequenza di smaltimento (qui pari a quella di offerta [305] [305]Non può essere λs>λo, perchè si servirebbero più richieste di quante se ne presentano. Se fosse invece λs<λo, la coda crescerebbe inesorabilmente e sarebbe quindi inutile.), e tempo medio di permanenza; infatti accade che N=L, ed utilizzando il risultato L=(Ao)/(1 −Ao) si ottiene
τp=(N)/(λs)=(L)/(λo)=(Ao)/(1 −Ao)(1)/(λo)=(λo)/(μ)(1)/(λo)(1)/(1  −λo⁄μ)=(1)/(μ−λo)
da cui si osserva che, se la frequenza di offerta tende al valore della frequenza di servizio, il tempo medio di permanenza tende ad ∞.
Tempo medio di codasi calcola come
τc=τp−τS=(1)/(μ−λo)−(1)/(μ)=(μ−μ+λo)/(μ(μ−λo))=(Ao)/(μ(1 −Ao))=(1)/(μ)(ρ)/(1 −ρ)=τS(ρ)/(1 −ρ)
Questo risultato mostra che il tempo medio di coda è legato al tempo medio di servizio e all’efficienza di giunzione, confermando ancora i risultati per ρ→ ∞.
La fig. 8.13↓ mostra l’andamento delle grandezze appena calcolate.
Figura 8.13 Grandezze di interesse per il sistema a coda infinita ed unico servente

### 8.4.3Sistemi a coda finita↓ e con più serventi

Riportiamo solo i risultati, validi se entrambi i processi di ingresso e di servizio sono esponenziali con frequenza media λo e μ, la coda è lunga L, i serventi sono M e le sorgenti infinite.
Probabilità di k richieste nel sistema
pk(Ao)=⎧⎨⎩ (Ako)/(k!α(Ao)) 0 ≤k≤M (Ako)/(Mk−MM!α(Ao)) M≤k≤M+L
in cui α(Ao)=(1)/(p0(Ao))=∑M+Lk= 0(Ako)/(k!) e Ao=(λo)/(μ). Si noti come per 0  ≤k≤M ed L= 0 si ottenga lo stesso risultato già esposto per i sistemi orientati alla perdita, mentre per M= 1 ed L= ∞ ci si riconduca al caso precedentemente analizzato.
Probabilità di ritardo↓
Pr=M+L⎲⎳k=Mpk(Ao)=pM(Ao)(1 −ρL+ 1)/(1 −ρ) in cui ρ=(Ao)/(M)
Probabilità di perdita
Pp=pM+L(Ao)=(AM+Lo)/(MLM!⋅α(Ao))
Tempo medio di coda↓
τc=τS(Pr−L⋅PM+L(Ao))/(M−Ao)
La Figura 8.14↓ descrive la probabilità di perdita per un sistema a servente singolo (a sinistra) e con 10 serventi (a destra), in funzione dell’intensità di traffico offerto e della lunghezza di coda, così come risulta dalla applicazione delle formule riportate. Nel caso di trasmissione di pacchetti di lunghezza fissa, per i quali il tempo di servizio è fisso e non a distribuzione esponenziale [306] [306]In una trasmissione a pacchetto, operata a frequenza binaria fb e con pacchetti di lunghezza media Lp bit, il tempo medio di servizio per un singolo pacchetto è pari a quello medio necessario alla sua trasmissione, e cioè τS=Lp⁄fb., i risultati ottenuti costituiscono una stima conservativa delle prestazioni del sistema (che potranno cioè essere migliori). L’analisi delle curve permette di valutare con esattezza il vantaggio dell’uso di una coda (a spese del tempo di ritardo). Infatti, aumentando il numero di posizioni di coda si mantiene una probabilità di blocco accettabile anche per traffico intenso.
Figura 8.14 Probabilità di perdita per un sistema a coda finita con uno o dieci serventi
Ad esempio, per Pb= 1% ed M= 1, osserviamo che una coda con L= 20 posizioni gestisce un traffico di Ao= 0.83 Erlang, contro gli Ao= 0.11 Erlang del caso senza coda. Ciò corrisponde ad un aumento dell’efficienza di (0.83)/(0.11)= 7.54 volte. D’altra parte ora il tempo medio di coda (calcolato in modo conservativo applicando la relazione per coda infinita) è τc=τS(ρ)/(1 −ρ)=(0.83)/(1 − 0.83)τS= 4.9τS, ed è quindi aumentato (rispetto a τS) di quasi 5 volte.
Esercizio Un nodo di una rete per dati effettua la multiplazione di pacchetti di dimensione media di 8 Kbyte [307] [307]1 byte = 8 bit, 1 K = 210= 1024. Il “K” in questione è “un K informatico”. Nel caso invece in cui ci si riferisca ad una velocita’ di trasmissione, il prefisso K torna a valere 103= 1000. su collegamenti con velocità binaria fb= 100 Mbps [308] [308]In virtù di quanto esposto alla nota precedente, in questo caso 1M= 106= 1000000.

- 1) Determinare il tempo medio di servizio di ogni singolo pacchetto;
  2) determinare il tempo medio di interarrivo τa tra pacchetti corrispondente ad un traffico di ingresso di 1200 pacchetti/secondo, e l’associata intensità Ao;
  3) assumendo che la dimensione dei pacchetti sia una v.a. con densità esponenziale negativa, così come il tempo di interarrivo tra pacchetti, e che la memoria del multiplatore sia così grande da approssimare le condizioni di coda infinita, determinare il ritardo medio di un pacchetto, ossia il tempo medio trascorso tra quando un pacchetto si presenta in ingresso al nodo e quando ne esce;
  4) calcolare la quantità di memoria necessaria ad ospitare i dati che si accumulano in un intervallo temporale pari al ritardo medio, considerando pacchetti di lunghezza fissa e pari alla media.

Risposte

- 1) Il tempo medio di servizio di un pacchetto è pari al tempo occorrente per trasmetterlo: τS=(1)/(μ)=durata di un bit⋅(bit)/(pacchetto)=(1)/(108)⎡⎣(secondi)/(bit)⎤⎦⋅1024⎡⎣(byte)/(pacchetto)⎤⎦⋅8⎡⎣(bit)/(byte)⎤⎦≃655μsec;
  2) τa=(1)/(λ)=(1)/(1200)= 833μsec; Ao=(λ)/(μ)= 1200⋅655⋅10− 6= 0.786 Erlang;
  3) Le condizioni poste corrispondono a quelle di traffico poissoniano e sistema a singolo servente e coda infinita, per il quale la teoria fornisce per il tempo di permanenza il risultato τp=(1)/(μ−λo)=(1)/((106)/(655)−(106)/(833))=(1)/(326)≃3 msec;
  4) La memoria necessaria è pari al prodotto tra il tempo medio di permanenza ed il numero di bit che si accumulano in quel periodo, ovvero 3⋅10− 3[sec]⋅1200⎡⎣(pacch)/(sec)⎤⎦⋅1024⎡⎣(byte)/(pacch)⎤⎦≃3.7 Kbyte.

PrecSezione 8.3: Sistema di servizio orientato alla perdita SuCapitolo 8: Traffico, code e reti a pacchetto Sezione 8.5: Reti per trasmissione datiSegue